package com.gofaraway.service.student.leetcode;

/**
 * 反转链表
 *
 * @author ChenPeng
 * @Date 2024/6/16 23:08
 */
public class Demo04 {

    /**
     * 给你单链表的头节点 head ，请你反转链表，并返回反转后的链表
     *
     * @param head
     * @return
     */
    public ListNode reverseList(ListNode head) {

        if (head == null || head.next == null) {
            return head;
        }

        ListNode newHead = reverseList(head.next);
        head.next.next = head;
        head.next = null;
        return newHead;


    }

    /**
     * 在遍历链表时，将当前节点的 next 指针改为指向前一个节点。
     * 由于节点没有引用其前一个节点，因此必须事先存储其前一个节点。'
     * 在更改引用之前，还需要存储后一个节点。最后返回新的头引用。
     *
     * @param head
     * @return
     */
    public ListNode reverseList1(ListNode head) {
        //单反转链表
        ListNode prev = null;
        ListNode curr = head;
        while (curr != null) {
            //存下 下一个节点
            ListNode next = curr.next;
            curr.next = prev;
            prev = curr;
            curr = next;
        }
        return prev;
    }

    public ListNode reverseList3(ListNode head) {
        ListNode pre = null;
        ListNode curr = head;

        while (curr != null) {
            ListNode next = curr.next;
            //翻转  当前节点指向前节点
            curr.next = pre;
            //开始移位 前节点变为当前节点
            pre = curr;
            //当前节点移到下一节点
            curr = next;
        }
        return pre;
    }

    public ListNode reverseList2(ListNode head) {
        ListNode pre = null;
        ListNode curr = head;

        while (curr != null) {
            ListNode next = head.next;
            //当前节点 的下一节点 指向前节点
            curr.next = pre;
            //准备移位 前节点 指向当前节点
            pre = curr;
            //当前节点 指向下一节点
            curr = next;
        }
        return pre;
    }


    public ListNode reverseList4(ListNode head) {
        ListNode pre = null;
        ListNode curr = head;
        while (curr != null) {
            ListNode next = curr.next;
            curr.next = pre;
            pre = curr;
            curr = next;
        }
        return pre;
    }


    public ListNode reverseList5(ListNode head) {
        ListNode curr = head;
        ListNode next = head.next;
        if(next==null)
            return  head;
        while (next != null) {
            ListNode nextnext = next.next;

            next.next = curr;
            if(nextnext==null){
                return next;
            }

            curr = nextnext;
            next=nextnext.next;
        }
        return next;
    }

    public ListNode reverseList6(ListNode head) {
        //反转链表 双指针反转
        ListNode pre = null;
        ListNode curr = head;
        while (curr != null) {
            ListNode next = curr.next;
            curr.next = pre;
            pre = curr;
            curr = next;
        }
        return pre;
    }

    public ListNode reverseList7(ListNode head) {
        ListNode pre = null;
        ListNode curr = head;
        while (curr != null) {
            ListNode next = curr.next;
            curr.next = pre;
            pre = curr;
            curr = next;
        }
        return pre;
    }
}

class ListNode {
    int val;
    ListNode next;

    ListNode() {
    }

    ListNode(int val) {
        this.val = val;
    }

    ListNode(int val, ListNode next) {
        this.val = val;
        this.next = next;
    }

}

//
//
///**
// * @author ChenPeng
// * @Date 2024/8/9 15:06
// */
//public class Demo04 {
//
//
//    /**
//     * 盛最多水的容器
//     * <p>
//     * 给定一个长度为 n 的整数数组 height 。有 n 条垂线，第 i 条线的两个端点是 (i, 0) 和 (i, height[i]) 。
//     * 找出其中的两条线，使得它们与 x 轴共同构成的容器可以容纳最多的水。
//     * 返回容器可以储存的最大水量。
//     * 说明：你不能倾斜容器。
//     */
//    public int maxArea(int[] height) {
//
//        int ans = 0;
//        //左指针
//        int l = 0;
//        //右指针
//        int r = height.length - 1;
//
//        while (l < r) {
//            int temp = Math.min(height[l], height[r]) * (r - l);
//            ans = Math.max(temp, ans);
//            if (height[l] < height[r]) {
//                l ++;
//            } else {
//                r --;
//            }
//        }
//        return ans;
//    }
//}

